package LeetCode.Heap;

import java.util.Arrays;

/**
 * @author : LdLtd
 * @Date : 2023/9/12
 * @Description:堆排序
 */
public class Heapsort {
    public static void main(String[] args) {
       int[] ar= new int[]{1,3,2,4,7,1,5};
        buildHeap(ar,ar.length);
        sort(ar,ar.length);
        Arrays.stream(ar).forEach(num -> System.out.print(num + " "));
    }
    /*建堆*/
    public static void buildHeap(int [] ar,int n){
        /*只要是非叶节点的根节点即可  (n-1)/2或者 n/2都可以 */
        for (int i = n/2-1; i >=0 ; i--) {
            heapify(ar,i,n);
        }
    }
    /*调整*/
    public static void heapify(int [] ar,int i,int size){
        /*i的左右孩子分别是 i*2+1  i*2+2*/
            int l=i*2+1,r=i*2+2,lar=i;
            if(l<size&&ar[l]>ar[lar]){
                lar=l;
            }
            if(r<size&&ar[r]>ar[lar]){
                lar=r;
            }
            if(lar!=i){
                swap(ar,i,lar);
                heapify(ar,lar,size);
            }
    }
    /*排序*/
    public static void sort(int []ar,int size){
        for (int i = size-1; i >0 ; i--) {
                swap(ar,i,0);
                //交换后，每次把最大的值放入数组的最后一个位置，并且再调整时，不调整后面的位置
                heapify(ar,0,i);
        }
    }
    /*交换*/
    public static void swap(int [] ar,int i,int j){
        int t=ar[i];
        ar[i]=ar[j];
        ar[j]=t;
    }
}
